// 解题思路：
// 根据字符串 s 中的字符，排列 0 ~ n 中的数字
// 如果是 ‘I’ 下一个数字增大，如果是 'D' 下一个数字减小
// 贪心策略：如果是 ‘I’ 先选个剩余最小的，如果是 ‘D’ 选一个剩余最大的

public class Solution {
    public int[] diStringMatch(String s) {
        int n = s.length();
        char[] sArr = s.toCharArray();
        int[] perm = new int[n + 1];
        int left = 0; int right = n;

        for(int i = 0; i < n; i++){
            if(sArr[i] == 'I'){
                perm[i] = left++;
            }else{
                perm[i] = right--;
            }
        }
        perm[n] = left;
        return perm;
    }
}
